package 背包问题;

import org.junit.Test;

/**
 * @Classname AllPackage
 * @Description TODO
 * @Date 2022/3/25 17:18
 * @Created by xjl
 */
public class AllPackage {
    /**
     * @description ks(i, t) = max{ks(i-1, t - V[i] * k) + P[i] * k}; （0 <= k * V[i] <= t）
     * @param: v
     * @param: w
     * @param: k
     * @param: c
     * @date: 2022/3/25 17:20
     * @return: int
     * @author: xjl
     */
    private int AllPackage(int[] v, int[] w, int n, int c) {
        int[][] result = new int[n + 1][c + 1];
        // 正式的1行1列的时候
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c; j++) {
                //判断是否能装下该容量
                if (j < w[i]) {
                    result[i][j] = result[i - 1][j];
                } else {
                    //表示的可以选择很多个0 1 2 最多是k个
                    for (int k = 0; k * v[i] <= j; k++) {
                        result[i][j] = Math.max(result[i - 1][j], result[i - 1][j - k * w[i]] + k * v[i]);
                    }
                }
            }
        }
        return result[n][c];
    }

    @Test
    public void TestAllPackage() {
        int[] w = {0, 5, 8};
        int[] V = {0, 5, 7};
        int k = 2;
        int c = 10;
        int i = AllPackage(w, w, k, c);
        System.out.println(i);

    }
}
